from sklearn import datasets
import numpy as np
import random
import matplotlib.pyplot as plt
import time
import copy


def find_neighbor(j, x, eps):
    N = list()
    temp = np.sum((x-x[j])**2, axis=1)**0.5
    N = np.argwhere(temp <= eps).flatten().tolist()
    return set(N)


def DBSCAN(X, eps, min_Pts):
    k = -1
    neighbor_list = []  # 用来保存每个数据的邻域
    omega_list = []  # 核心对象集合
    gama = set([x for x in range(len(X))])  # 初始时将所有点标记为未访问
    cluster = [-1 for _ in range(len(X))]  # 聚类
    for i in range(len(X)):
        neighbor_list.append(find_neighbor(i, X, eps))
        if len(neighbor_list[-1]) >= min_Pts:
            omega_list.append(i)  # 将样本加入核心对象集合
    omega_list = set(omega_list)  # 转化为集合便于操作
    print(neighbor_list, "neighbor_list===================================================")
    print(gama,"gama===================================================")
    print(omega_list,"omega_list===================================================")
    while len(omega_list) > 0:
        print("##########################################################################################################3")
        gama_old = copy.deepcopy(gama)
        print(gama_old, "gama_old===================================================")
        j = random.choice(list(omega_list))  # 随机选取一个核心对象
        print(j, "j===================================================")
        k = k + 1
        Q = list()
        Q.append(j)
        print(Q,"Q===================================================")
        gama.remove(j)
        print(gama, "gama===================================================")
        print("进入while len(Q) > 0")
        while len(Q) > 0:
            q = Q[0]
            print(q, "q===================================================")
            Q.remove(q)
            print(len(neighbor_list[q]) >= min_Pts)
            if len(neighbor_list[q]) >= min_Pts:
                print(q,"q***",neighbor_list[q], "neighbor_list[q]***********************************************")
                delta = neighbor_list[q] & gama
                deltalist = list(delta)
                print(deltalist, "deltalist***********************************************")
                for i in range(len(delta)):
                    Q.append(deltalist[i])
                    gama = gama - delta
        print("退出while len(Q) > 0")
        print(gama, "gama===================================================")
        print(Q,"Q===================================================")
        Ck = gama_old - gama
        Cklist = list(Ck)
        for i in range(len(Ck)):
            cluster[Cklist[i]] = k
        omega_list = omega_list - Ck
        print(omega_list,"omega_list===================================================")
        print(k)
        print(cluster)
    return cluster


X1, y1 = datasets.make_circles(n_samples=100, factor=.6, noise=.02)
X = X1
X = np.array([[ 0.32895736,-0.51221268],
 [-0.99552907,0.14495927],
 [-0.4829017,-0.35860553],
 [-0.03996099,-0.97974243],
 [ 0.17940332,-0.96849635],
 [-0.84011632,0.59794595],
 [-0.61078753,-0.00824691],
 [-0.87484394,0.40123703],
 [ 0.91750447,-0.37123595],
 [-0.52896986,-0.29893917],
 [ 0.52977523 ,0.28175415],
 [ 0.44681138,0.41102953],
 [-0.56907658,0.18021926],
 [-0.96565083,0.23420952],
 [ 1.0182326,-0.01000946],
 [-1.01474544,-0.11380731],
 [ 0.4181752,-0.40285348],
 [-0.18819795,-0.59499014],
 [ 0.4077187,-0.89937817],
 [ 0.08274884,-0.55559733],
 [-0.154021,-0.99302694],
 [-0.53896298,-0.84618822],
 [ 0.59298744,-0.82064683],
 [ 0.77990611,0.69204898],
 [-0.43505667,-0.44400838],
 [-0.32280474,0.51903906],
 [ 0.35595357,0.44304473],
 [ 0.56785718,-0.00773824],
 [-0.21374416,0.5552059 ],
 [-0.30874133,-0.53061184],
 [-0.59326018,0.08288957],
 [ 0.25178935,0.53810815],
 [-0.086698,0.56057624],
 [ 0.51188817,0.35265441],
 [ 0.02267623,0.59792026],
 [-0.43215638,-0.85023883],
 [ 0.33853378,0.50467104],
 [-0.59491874,-0.16863954],
 [-0.71577986,0.68195805],
 [ 0.95987341,-0.25700016],
 [ 0.80060841,0.62267333],
 [ 0.05342573,-0.98833343],
 [ 0.51575953,-0.3004148 ],
 [-0.63816997,0.77451735],
 [ 0.32999912,-0.94056677],
 [ 0.73860861,-0.68737569],
 [-0.98796434,-0.00171056],
 [-0.26285473,-0.57634382],
 [ 0.58339121,0.0446834 ],
 [-0.43007935,0.91501284],
 [ 1.03305021,-0.12235135],
 [-0.21948391,0.98461183],
 [ 0.55429227,0.16694243],
 [ 0.79066512,-0.58386247],
 [ 0.92951865,0.37507527],
 [-0.86829732,0.48055292],
 [ 0.87326067,-0.48774318],
 [-0.54390428,0.82504801],
 [ 0.60864293,0.76552658],
 [ 0.55678524,0.27611088],
 [-0.48712866,0.32083285],
 [-0.58425849,-0.07917727],
 [ 0.05481627,-0.58480341],
 [-0.92257522,-0.23360473],
 [ 0.09506982,0.5856497 ],
 [-0.32387097,0.94270843],
 [ 0.59210977,-0.21317059],
 [ 0.45524967,-0.32451617],
 [ 1.02422382,0.10961374],
 [ 0.59239455,-0.159749  ],
 [ 0.17480891,-0.59830126],
 [ 0.20817412,0.58182311],
 [ 0.2505053,-0.52316998],
 [-0.11504775,-0.56843186],
 [-0.6445064,-0.77072734],
 [ 0.20218437,0.95376889],
 [ 0.40245271,-0.46885983],
 [-0.29546764,-0.94729903],
 [ 0.97017993,0.2430411 ],
 [-0.53946255,0.28495867],
 [ 0.58289787,-0.06553209],
 [-0.88679624,-0.45878767],
 [-0.36821004,0.47646409],
 [-0.0880127,0.95403125],
 [-0.92287891,-0.35543225],
 [-0.02799583,-0.57672435],
 [-0.56596516,0.22943232],
 [ 0.89088093,0.47542757],
 [ 0.30134362,0.94010258],
 [-0.01957044,0.59512561],
 [ 0.09849566,0.97252586],
 [-0.54339026,-0.20356505],
 [ 0.53588121,0.84283912],
 [ 0.59989507,-0.76314187],
 [ 0.45497841,0.92386693],
 [-0.82153256,-0.65253037],
 [-0.42721421,0.42537628],
 [-0.15992467,0.57388402],
 [-0.76603251,-0.68726938],
 [-0.3854191,-0.47149624]])
print(X)
eps = 0.08
min_Pts = 3
begin = time.time()
C = DBSCAN(X, eps, min_Pts)
end = time.time()
plt.figure()
plt.scatter(X[:, 0], X[:, 1], c=C)
plt.show()
